package newcoder_exp.justPractise;

import java.util.Arrays;

import org.junit.Test;

public class Pra1_LongestSubArray {
    //最长公共子串

    /* 
        f[i - 1][j - 1] 绝对没有 f[i - 1][j] 或者 f[i][j - 1]大
        而f[i - 1][j - 1] + 1绝对大于等于f[i - 1][j] 或者 f[i][j - 1]
    */
    public String longesString(String s1, String s2) {
        int len1 = s1.length(), len2 = s2.length();
        char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray();
        int[][] f = new int[len1 + 1][len2 + 1], 
        p = new int[len1 + 1][len2 + 1];
        //f[0][0] f[0][j] f[i][0]默认为0
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (cs1[i - 1] == cs2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                    p[i][j] = 1;
                } else {
                    if (f[i - 1][j] > f[i][j - 1]) {
                        p[i][j] = 2; //等于2，取得是上面的值
                        f[i][j] = f[i - 1][j];
                    } else {
                        p[i][j] = 3; //等于3，取左边的值
                        f[i][j] = f[i][j - 1];
                    }
                }
            }
        }
        System.out.println(Arrays.deepToString(f));
        System.out.println(Arrays.deepToString(p));

        //第三个参数决定了子串结果是哪个（若有多组解的情况）
        String res = find(len1, len2, s1, p);
        return res;
    }

    private String find(int i, int j, String s, int[][] p) {
        if (i == 0 || j == 0) {
            return "";
        }
        String res = null;
        if (p[i][j] == 1) {
            res = find(i - 1, j - 1, s, p) + "" + s.charAt(i - 1);
        } else if (p[i][j] == 2) {
            res = find(i - 1, j, s, p);
        } else {
            res = find(i, j - 1, s, p);
        }
        return res;
    }

    @Test
    public void test() {
        System.out.println(longesString("2LQ74WK8Ld0x7d8FP8l61pD7Wsz1E9xOMp920hM948eGjL9Kb5KJt80","U08U29zzuodz16CBZ8xfpmmn5SKD80smJbK83F2T37JRqYfE76vh6hrE451uFQ100ye9hog1Y52LDk0L52SuD948eGjLz0htzd5YF9J1Y6oI7562z4T2"));
    }
    /* 
        场景：用户点击登录页面的第三方登录，如QQ，会弹出一个小的浏览器页面，地址栏可以看出来是一个get请求，
        之后填入账号密码可以利用第三方的信息登录进入系统
        
        1. 用户点击第三方登录请求，
    */
}
